So, welcome for Computer Graphics.

We are currently speaking about ray tracing and last week you learned about the basics

of ray tracing, about irays that we shoot from the camera and about secondary rays that

we use to obtain indirect effects like shadows, reflections and so forth.

And at the core of all these methods is always the operation to cast a ray.

And this operation is pretty simple, given a ray with a starting point and a direction

we want to find the first intersection of that ray with any scene object.

It's a geometrically rather simple operation, but it's also rather costly.

At least if we do it naively that means if we intersect our ray with all the objects

in the scene with all the triangles in the scene, if we have 1 million triangles then

this means we have to intersect a single ray with 1 million triangles and we have many

rays, billions of rays that we need to generate such an image.

It's not only the irays, but also all the secondary rays and I also told you about methods

where we have multiple irays per pixel and also for the secondary rays the number can

grow very quickly, so having 1,000 rays for a single pixel is not unusual.

That means if we have 2 million pixels on our screen we would need 2 billion rays and

if for each of these 2 billion rays we have to intersect with 1 million triangles and

if we do that naively that becomes very costly.

So we have to look at how can we accelerate these ray operations, these ray computations

and in fact there are two things we can look into.

The first one is how can we as fast as possible compute the intersection between a single

ray and a primitive, a triangle or a sphere or so.

We were looking at that last week and the other one how can we reduce the number of

tests.

How can we for a single ray to find the intersections, how can we test with only as few objects

as possible and so reduce the number of intersection tests and in fact this is what we will speak

about today.

How can we for a given ray, how can we quickly determine which objects might or which triangles

might be in the way of that ray and only check these much hopefully much fewer triangles.

Just again to, I mean I already spoke about these numbers, if we make plain ray casting

that means for each we have the outer loop is that for each of the NP pixels or I think

we used M in the last lecture and we test each of these irays against each of the N

scene primitives then we have two nested loops and altogether we have complexity of number

of pixels, time number of objects and as I said this can be very very very big number

and yeah so we have to do that faster and in the end ideally yeah so testing a single

ray with a scene if we do it naively it would be O of N that means proportional to the number

of objects in the scene but the goal today will be to end up with algorithms that are

have a complexity of O of log N yeah like a search process and yeah this would, this

is required to make ray tracing practical.

Okay and as I said it's very important about more than 90% of the computation time of ray

tracers usually goes into these intersection tests and yeah so we somehow have to accelerate

that and usually we do that by building up a data structure, acceleration data structure

that allows us to do that ray traversal faster and yeah this data structure needs to be very

quickly built in the very beginning so we take the entire scene yeah build a data structure

and acceleration data structure on top of this entire scene and hopefully then we can

cast our rays faster and of course building up the data structure alone will be a rather

costly process and this process should not be too complicated yeah because otherwise

if we have a process for building up our acceleration data structure that is O of N squared we gain

nothing yeah because then we have an O of N operation that is accelerated by something

which is O of N squared yeah so we need to have a pre-processing that also should be